package com.hyc.DataStructure.sort;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.sort
 * @className: QuickSort
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/1/21 22:44
 * @version: 1.0
 */
public class QuickSort {
    public static void main(String[] args) {
        int arr[] = {-9, 78, 0, 23, -567};
        int[] test = new int[8000000];
        //测试数据
        for (int i = 0; i < 8000000; i++) {
            test[i] = (int) (Math.random() * 800000);
        }
        long time = System.currentTimeMillis();
        quickSort1(arr, 0, arr.length - 1);
        long end = System.currentTimeMillis();
        long t = ((end - time) / 1000);
        System.out.println("一共用时 " + t + "秒");
    }


    public static void quickSort1(int[] a, int l, int r) {

        if (l < r) {
            int i, j, x;

            i = l;
            j = r;
            x = a[i];
            while (i < j) {
                while (i < j && a[j] > x) {
                    j--; // 从右向左找第一个小于x的数
                }
                if (i < j) {
                    a[i++] = a[j];
                }
                while (i < j && a[i] < x) {
                    i++; // 从左向右找第一个大于x的数
                }
                if (i < j) {
                    a[j--] = a[i];
                }
            }
            a[i] = x;
            quickSort(a, l, i - 1); /* 递归调用 */
            quickSort(a, i + 1, r); /* 递归调用 */
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        //  left index
        int l = left;
        int r = right;
        //    pivot 中轴值
        int pivot = arr[(left + right) / 2];
        //临时变量
        int temp = 0;
        //    while 循环的目的是比比中轴的pivot值小的放在左边
        //    比pivot 值大的放在右边
        while (l < r) {
            //    在pivot的左边一直寻找 找到大于等于pivot 的值才退出
            while (arr[l] < pivot) {
                l += 1;
            }
            //    在pivot的右边一直寻找 找到小于等于pivot 的值才退出
            while (arr[r] > pivot) {
                r -= 1;
            }
            //    如果 l>=r说明pivot的左右两个值已经按照左边全都是小于等于pivot，右边去哪不是大于等于pivot排列好了
            if (l >= r) {
                break;
            }
            //    交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //    如果交换玩发现这个arr[l]==pivot值 相等r--前移
            if (arr[l] == pivot) {
                r -= 1;
            }
            //如果交换玩发现 arr[r] == pivot值 相等l++ 后移
            if (arr[r] == pivot) {
                l += 1;
            }
        }
        //    如果l==r 必须是 l++ r-- 否则会出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if (right > l) {
            quickSort(arr, l, right);
        }
    }
}

